package com.lw.leetcode.binary.b;

/**
 * 1300. 转变数组后最接近目标值的数组和
 *
 * @Author liw
 * @Date 2021/6/12 14:14
 * @Version 1.0
 */
public class FindBestValue {


    public static void main(String[] args){
        FindBestValue test = new FindBestValue();
        // 50  15
//        int[] arr = {15,1,1,1,1,1,1,1,1,1,1,1};
        // 56803  11361
//        int[] arr = {60864,25176,27249,21296,20204};
        // 10  3
        int[] arr = {4,9,3};
        // 10  5
//        int[] arr = {2,3,5};
        int bestValue = test.findBestValue(arr, 10);
        System.out.println(bestValue);
    }

    public int findBestValue(int[] arr, int target) {
        int st = 0;
        int end = 0;
        for (int i : arr) {
            end = Math.max(i, end);
        }
        long min = Integer.MAX_VALUE;
        long c ;
        int value = 0;


        while (st <= end) {
            int m = st + ((end - st) >> 1);
            long sum = getSum(arr, m);
            if (sum > target) {
                end = m - 1;
                c =  sum - target;
            } else {
                st = m + 1;
                c = target - sum;
            }
            if (c < min || (c == min && value > m)) {
                min = c;
                value = m;
            }
        }
        return value;
    }

    private long getSum (int[] arr, int value) {
        long sum = 0;
        for (int i : arr) {
            sum += (i > value ? value : i);
        }
        return sum;
    }


}
